package algorithms.leaning.class31;

import common.util.MyUtil;

/**
 * 给定一个数组arr，用户希望你实现如下三个方法
 * 1）void add(int L, int R, int V) :  让数组arr[L…R]上每个数都加上V
 * 2）void update(int L, int R, int V) :  让数组arr[L…R]上每个数都变成V
 * 3）int sum(int L, int R) :让返回arr[L…R]这个范围整体的累加和
 * 怎么让这三个方法的时间复杂度都是O(logN)
 *
 * @author guichang
 * @date 2021/7/4
 */

@SuppressWarnings("all")
public class Code1_线段树_实现 {

    public static void main(String[] args) {
        int[] array = MyUtil.createArray(1, 2, 3, 4, 5, 6, 7, 8, 9);
        SegmentTree st = new SegmentTree(array);
        st.add(2, 3, 10);
        st.update(5, 6, 99);
        int sum = st.sum(1, 8);
        MyUtil.print(sum);
    }

    /**
     * TODO 线段树实现类
     */
    public static class SegmentTree {

        public SegmentTree(int[] array) {

        }

        public void add(int L, int R, int V) {

        }

        public void update(int L, int R, int V) {

        }

        public int sum(int L, int R) {
            return -1;
        }

    }

}